#include <stdlib.h>
#include <assert.h>
#include <stdio.h>
#include <string.h>

typedef unsigned int	uint32_t;
typedef unsigned char	uint8_t;

typedef struct BitMap{
	uint32_t	*bitmap;	//实际位图空间
	int			num;        //存储元素个数
	int			size;		//指明该位图bit位数
}BitMap;

//位图初始化
void BMInit(BitMap *bm){
	bm->size = 0;
	bm->num = 0;
	bm->bitmap = (uint32_t *)malloc(sizeof(uint32_t)* 1);
	assert(bm->bitmap);
	memset(bm->bitmap, 0x0, sizeof(uint32_t)* 1);
	printf("初始化完成\n");
}

//位图创建
void BMCreat(BitMap *bm, unsigned int bitnum){
	//printf("%u",bitNum);
	bm->size = bitnum;
	unsigned int num = bm->size / 32;
	num += (bm->size % 32) ? 1 : 0;

	bm->bitmap = (uint32_t *)malloc(sizeof(uint32_t)* num);
	assert(bm->bitmap);
	bm->num = num;

	memset(bm->bitmap, 0x0, sizeof(uint32_t)* num);
	printf("位图创建化完成,位图大小位%ubit\n",bm->size);
}

//位图bit置1
void BMSet1(BitMap *bm, unsigned int which){
	assert(which < bm->size);

	unsigned int index = which / 32;
	unsigned int bit = which % 32;

	bm->bitmap[index] |= (1 << bit);
}

//计数
unsigned int Count(BitMap *bm){
	unsigned int count = 0;
	int i, j;
	uint8_t ch;
	unsigned char *table = "\0\1\1\2\1\2\2\3\1\2\2\3\2\3\3\4";

	for (i = 0; i < bm->num; i++) {
		for (j = 0; j < sizeof(uint32_t); j++) {
			ch = 0xFF & (bm->bitmap[i] >> j * sizeof(uint8_t));
			count += table[ch & 0xF];
			count += table[(ch >> 4) & 0xF];
		}
	}

	return count;
}

//释放空间
void BMDestroy(BitMap *bm){
	free(bm->bitmap);
}
